package main

// 118. 杨辉三角
func main() {
	row := 5
	array := generate(row)
	for _, i := range array {
		for _, j := range i {
			print(j)
		}
		println()
	}
}

func generate(numRows int) [][]int {
	var res [][]int
	if numRows > 0 {
		res = append(res, []int{1})
	}
	for i := 1; i < numRows; i++ {
		preRow := res[i-1]
		var newRow []int
		newRow = append(newRow, preRow[0])
		for j := 0; j < len(preRow)-1; j++ {
			newRow = append(newRow, preRow[j]+preRow[j+1])
		}
		newRow = append(newRow, preRow[len(preRow)-1])
		res = append(res, newRow)
	}
	return res
}

// 最快解，预算设置了array的长度
func generateM(numRows int) [][]int {
	c := make([][]int, numRows)
	for i := range c {
		c[i] = make([]int, i+1)
		c[i][0], c[i][i] = 1, 1
		for j := 1; j < i; j++ {
			// 左上方的数 + 正上方的数
			c[i][j] = c[i-1][j-1] + c[i-1][j]
		}
	}
	return c
}

//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
//
//在「杨辉三角」中，每个数是它左上方和右上方的数的和。
//
//示例 1:
//
//输入: numRows = 5
//输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
//
//示例 2:
//输入: numRows = 1
//输出: [[1]]
//
//
//提示:
//
//1 <= numRows <= 30
